The present invention relates to providing a digital fingerprint for an electronic document.
Due to the rapid growth of the Internet and the resulting possibility of digital dissemination of documents, there is growing demand for ways to prevent illegal dissemination of documents and to protect copyright holders against the problems associated with pirated copies.
To this end, big companies such as IBM, NEC and Microsoft, along with smaller firms such as Digimarc (see Funkschau 17/97, p. 21) and research institutes such as the Fraunhofergesellschaft IGD and GMD Darmstadt, are working on ways to embed digital watermarks in documents. In methods of this kind, data which indicate the identity of the copyright holder are invisibly embedded in the documents to be protected. The type of digital watermark embedded varies according to the type of document (e.g., Postscript, JPEG, MPEG-1).
With digital watermarks, the copyright holder can produce evidence that a given document is his own intellectual property, by comparing it with an illegally disseminated document. However, with digital watermarks it is impossible to determine the identity of the illegal disseminator or to prove that he has indeed carried out illegal dissemination.
Digital fingerprints go one step further. When a document is secured using digital fingerprinting, the name of the customer who is to receive the electronic copy of the document is invisibly embedded in the document, along with the copyright holder""s digital watermark. If this customer disseminates his copy contrary to the interests of the copyright holder, he can be unambiguously identified based on his electronic fingerprint, which will be contained in all of the illegally disseminated copies, and he can therefore be held accountable (Dan Boneh and James Shaw, Collusion-Secure Fingerprinting for Digital Data. Proc. CRYPTO 95, LNCS 963, Springer Verlag, Berlin (1995), pages 452-465.)
Until now, digital fingerprinting for protecting documents has had a serious weakness, in that the bit patterns of documents assigned to given customers differ at precisely the position where the customer""s user-specific fingerprint is provided. If the customer gains possession of a second customer""s document, or a group of lawbreakers collude, they can, by comparing the two documents bit by bit, find the positions at which the differing digital fingerprints are provided and delete them from the document. Using a method described in German Patent Application No. 19816356.8, which is hereby incorporated by reference herein, one can use overlapping finite geometric structures to partially prevent efforts to acquire a copy of the document from which all user-specific fingerprints have been removed. With reference to FIG. 1, because intersection S of fingerprints A, B and C is identical, cannot be found, and is left intact, detective work is possible. However, if the number of lawbreakers is large, detective work of this kind is difficult, and the results can be ambiguous.
An object of the present invention is to eliminate this shortcoming, so that a larger number of copies of documents is feasible, and so that one can trace even larger groups of lawbreakers more effectively.
The present invention provides a method for embedding manipulation-secure digital fingerprints in electronic documents, wherein a copy of a document in which an individual fingerprint unrecognizable to the buyer has been embedded as an identifier is assigned to each buyer, assignment of the flagging positions of the individual digital fingerprint, which is different for each copy, being based on finite geometric structures as described in German Patent Application No. 19816356.8. Each buyer""s copy is flagged at positions defined by the geometric substructure assigned to that buyer and by a secret function, and the points thus established as the buyer""s digital fingerprint are defined within the geometric structure so that they intersect with the points of the fingerprints of other buyers, it being possible, by comparing the original document bit by bit with a copy from which fingerprint components have been removed via collusion among a maximum of d buyers, to use the remaining intersections of fingerprints to trace the copies involved in the collusion and hence trace the buyers who have become lawbreakers. The present invention is characterized in that one point in the projective space PG (d, q) of hyperplanes is unambiguously assigned to each flagging position in the document via a secret function, at least two hyperplanes of PG (d, q) are assigned to each fingerprint, each being exclusively assigned to one fingerprint only, and for each fingerprint, precisely those flagging positions that correspond to the points of the selected hyperplane are flagged.
According to an embodiment of the present invention, in order to trace attempts to delete fingerprints the geometric objects are reconstructed from the flagged flagging positions that have been found in the document, by analyzing the linear dependencies one determines in which hyperplanes the objects are contained, and by calculating these hyperplanes one gradually determines the fingerprints of the colluding customers.